BOJ_1912_연속합

DP(Dynamic Programming)를 사용해서 구간의 연속합 충 최대를 구하는 문제
최대 부분합 문제라고도 부르며, Kadane's 알고리즘이라고도 부른다
시간복잡도는 O(n)이다

dp[n] : n까지의 구간 최댓값

이 문제는 dp배열 뿐만 아니라 구간의 합계를 저장하는 변수가 필요하다
단순하게 누적합을 저장하는 것은 아니다

range_sum : 누적합을 저장한다. 만약 누적합 + nums[i]가 nums[i]보다 작다면, i부터 누적을 새로 시작한다

즉,

1. i-1까지의 누적합 + nums[i] -> 기존 구간 확장
2. nums[i] -> 새로운 구간 시작
   중에 더 큰 것을 range_sum으로 넣는 것이다

위에서 이에 대한 연산을 진행했을 때, dp 점화식은 다음과 같다
dp[i] = max(dp[i - 1], range_sum)

알게된 것

파이썬에서 최대, 최소를 초기화 할 때 float('inf'), float('-inf')를 사용한다

n = int(input())  
nums = list(map(int, input().split()))  
nums.insert(0, 0)  
  
dp = [float('-inf')] * (n + 1)  
dp[1] = nums[1]  
  
range_sum = nums[1]  
for i in range(2, n + 1):  
    num = nums[i]  
  
    if range_sum + num < num:  
        # 다시 시작  
        range_sum = num  
  
    else:  
        # 이어가기  
        range_sum += num  
  
    dp[i] = max(dp[i - 1], range_sum)  
  
print(dp[n])